package com.hao.tree;


import java.io.*;
import java.util.*;

/**
 * TODO
 * 利用霍夫曼树进行压缩
 * @author 97472
 * @version 1.0
 * @date 2021/5/31 16:06
 */
public class HuffmanCode {
    // 1.创建一个Node节点类，里面保护data，权值weight，左节点和右节点
    // 2.将字符串变成byte数组
    // 3.统计字符出现的次数,并将他对应的Node放入List进行排序
    // 4.根据各个字符出现的次数来构建霍夫曼树
    // 5.根据霍夫曼树来确定各个字符的霍夫曼编码
    // 6.根据霍夫曼编码来编写二进制数据
    public static void main(String[] args) {
        byte[] bytes = "hello world".getBytes();
        for (int i = 0; i < bytes.length; i++) {
            System.out.print(" "+bytes[i]);
        }
//        byte[] sourceByte = "i like like like java do you like a java".getBytes();
//        byte[] desBytes = compressBinary(sourceByte);
//        System.out.println("hello world");
//        zipFile("D:\\project\\algorithm\\src\\main\\resources\\book.jpg" ,"D:\\project\\algorithm\\src\\main\\resources\\book.zip");
//        unzipFile("D:\\project\\algorithm\\src\\main\\resources\\book.zip" ,"D:\\project\\algorithm\\src\\main\\resources\\unzip.jpg");
    }
    public static void unzipFile(String source,String des){
        InputStream is = null;
        OutputStream os = null;
        try {
            // 从源文件中获取霍夫曼byte数组和霍夫曼编码
            is = new FileInputStream(source);
            ObjectInputStream ois = new ObjectInputStream(is);
            byte[] huffmanBytes = (byte[]) ois.readObject();
            huffmanCode = (Map<Byte, String>) ois.readObject();
            // 将其解码为byte数组
            byte[] bytes = unzip(huffmanBytes, huffmanCode);
            // 再将霍夫曼byte数据和对应的霍夫曼编码进行输出
            os = new FileOutputStream(des);
            os.write(bytes);
        }catch (Exception e){
            e.printStackTrace();
        }finally {
            if (is!=null){
                try {
                    is.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (os!=null){
                try {
                    os.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    public static void zipFile(String source,String des){
        InputStream is = null;
        OutputStream os = null;
        try {
            // 将从源文件其转换为byte数组
            is = new FileInputStream(source);
            byte[] fileDataByte = new byte[is.available()];
            is.read(fileDataByte);
            //将其压缩为霍夫曼数据
            byte[] huffmanBytes = compressBinary(fileDataByte);
            // 再将霍夫曼byte数据和对应的霍夫曼编码进行输出
            os = new FileOutputStream(des);
            ObjectOutputStream oos = new ObjectOutputStream(os);
            oos.writeObject(huffmanBytes);
            oos.writeObject(huffmanCode);
        }catch (Exception e){
            e.printStackTrace();
        }finally {
            if (is!=null){
                try {
                    is.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (os!=null){
                try {
                    os.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    /**
     * 霍夫曼编码
     */
    private static Map<Byte,String> huffmanCode;

    /**
     * 将普通的byte数据压缩为霍夫曼byte数据
     * @param strBytes
     * @return
     */
    public static byte[] compressBinary(byte[] strBytes){
        // 2.将字符串变成byte数组
        // 3.统计字符出现的次数,并将他对应的Node放入List进行排序
        List<Node> nodes = getNodes(strBytes);
        System.out.println("nodes:"+nodes);
        // 4.根据各个字符出现的次数来构建霍夫曼树
        Node root = parse(nodes);
        System.out.println("root:"+root);
        // 5.根据霍夫曼树来确定各个字符的霍夫曼编码
        huffmanCode = getHuffmanCode(root);
        System.out.println("huffmanCodeByByte:"+huffmanCode);
        // 6.根据霍夫曼编码来编写二进制数据
        return zip(strBytes,huffmanCode);
    }

    /**
     * 解压，根据压缩后的byte数组和对应的霍夫曼编码进行解码。
     * @param zipCode
     * @param huffmanCodeByByte
     * @return
     */
    public static byte[] unzip(byte[] zipCode,Map<Byte,String> huffmanCodeByByte){
        // 将zipCode转换为二进制字符串
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < zipCode.length; i++) {
            String binaryStr = Integer.toBinaryString(zipCode[i]);
            if (binaryStr.length() > 8){
                binaryStr = binaryStr.substring(binaryStr.length()-8,binaryStr.length());
            }else {
                for (int j = 0; j < 8-binaryStr.length(); j++) {
                    buffer.append("0");
                }
            }
            buffer.append(binaryStr);
        }
        // 将二进制字符串和霍夫曼树编码进行比较得到byte数组
        List<Byte> bytes = new ArrayList<>();
        Set<Map.Entry<Byte, String>> entries = huffmanCodeByByte.entrySet();
        boolean isOver = false;
        while (!isOver){
            isOver = true;
            for (Map.Entry<Byte, String> ele:entries) {
                if (buffer.toString().startsWith(ele.getValue())){
                    bytes.add(ele.getKey());
                    buffer.delete(0,ele.getValue().length());
                    isOver = false;
                    break;
                }
            }
        }
        // 将byte数组里的元素转换为一个一个字符连接起来的字符串
        byte[] chByte = new byte[bytes.size()];
        for (int i = 0; i < chByte.length ; i++) {
            chByte[i] = bytes.get(i);
        }
        return chByte;
    }
    /**
     * 压缩为一个数组
     * @param strBytes
     * @param huffmanCodeByByte
     * @return
     */
    private static byte[] zip(byte[] strBytes,Map<Byte,String> huffmanCodeByByte) {
        // 根据霍夫曼树编码和字符byte数组来获取压缩后的二进制字符串
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < strBytes.length; i++) {
            String code = huffmanCodeByByte.get(strBytes[i]);
            buffer.append(code);
        }
        System.out.println("二进制:"+buffer.toString());
        // 将二级制字符串转换为byte数组
        // 获取byte数组的大小（每个位置是8位，所以是buffer.length()/8+1）
        int byteLength = buffer.length()/8+1;
        byte[] code = new byte[byteLength];
        // 如果没满byteLength*8 就往后面添加0（确保byte数组每一个元素都是8位）
        for (int i = buffer.length(); i < byteLength*8; i++) {
            buffer.append('0');
        }
        for (int i = 0; i < buffer.length(); i += 8) {
            String byteStr;
            byteStr = buffer.substring(i,i+8);
            code[i/8] = (byte) Integer.parseInt(byteStr, 2);
        }
        return code;
    }

    /**
     * 获取霍夫曼编码
     * @param root 霍夫曼树的根节点
     * @return
     */
    private static Map<Byte, String> getHuffmanCode(Node root) {
        Map<Byte, String> huffmanCode = new HashMap<>();
        // 利用递归操作完成对霍夫曼编码
        getHuffmanCode(huffmanCode,"",root);
        return huffmanCode;
    }

    /**
     * 递归式获取霍夫曼编码的递归方法
     * @param huffmanCode
     * @param code
     * @param node
     */
    private static void getHuffmanCode(Map<Byte, String> huffmanCode,String code, Node node) {
        if (node.left==null && node.right==null){
            huffmanCode.put(node.data,code);
        }
        if (node.left!=null){
            String leftCode = code + "0";
            getHuffmanCode(huffmanCode,leftCode,node.left);
        }
        if (node.right!=null){
            String leftCode = code + "1";
            getHuffmanCode(huffmanCode,leftCode,node.right);
        }
    }
    /**
     * 解析节点集合变成霍夫曼树
     * @param arr 节点的集合
     * @return
     */
    private static Node parse(List<Node> arr){
        if (arr.size() > 1){
            // 进行排序
            Collections.sort(arr);
            // 头部的两个元素座位子节点创建一个树
            Node childNode0 = arr.get(0);
            Node childNode1 = arr.get(1);
            arr.remove(0);
            arr.remove(0);
            Node parentNode;
            if (childNode0.compareTo(childNode1) > 0){
                parentNode = new Node(null,childNode0.weight+childNode1.weight, childNode0, childNode1);
            }else {
                parentNode = new Node(null,childNode0.weight+childNode1.weight, childNode1, childNode0);
            }
            //添加到原数组中
            arr.add(parentNode);
            //在进行依次解析
            return parse(arr);
        }else {
            return arr.size() == 1?arr.get(0):null;
        }
    }

    /**
     * 将字符数组转换为Node节点集合
     * @param strBytes
     * @return
     */
    private static List<Node> getNodes(byte[] strBytes) {
        // 统计次数，利用map的原理
        Map<Byte,Integer> byteTime = new HashMap();
        for (int i = 0; i < strBytes.length; i++) {
            // 获取byte对应的次数，如果为null就设为1，否则就设为time+1
            Integer time = byteTime.get(strBytes[i]);
            if (time == null){
                time = 1;
            }else {
                time += 1;
            }
            byteTime.put(strBytes[i],time);
        }
        //创建利用统计次数来创建node集合
        List<Node> nodes = new ArrayList<>();
        Set<Map.Entry<Byte, Integer>> entries = byteTime.entrySet();
        entries.forEach(ele->{
            nodes.add(new Node(ele.getKey(),ele.getValue()));
        });
        return nodes;
    }

    static class Node implements Comparable<Node>{
        Byte data;
        Integer weight;
        Node left;
        Node right;

        public Node(Byte data, Integer weight) {
            this.data = data;
            this.weight = weight;
        }

        public Node(Byte data, Integer weight, Node left, Node right) {
            this.data = data;
            this.weight = weight;
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
